Mathématiques discrètes : Les bases du dénombrement

Le dénombrement est l'art de déterminer la taille d'un ensemble fini sans le travail fastidieux de l'énumération physique. En exploitant des structures logiques, nous pouvons résoudre des problèmes allant des combinaisons simples de menus aux permutations cryptographiques complexes.

La logique de « OU » et de « ET »

Deux piliers soutiennent l'ensemble du domaine de la combinatoire. Leur application dépend entièrement de la manière dont nous considérons une tâche : comme un choix unique parmi plusieurs catégories ou comme une suite de choix.

Le principe d'addition (règle de somme)

Si un ensemble $X$ est partitionné en sous-ensembles disjoints $X_1, X_2, \dots, X_n$, alors le nombre total d'éléments $|X|$ est la somme des tailles de ces sous-ensembles :

$$|X| = |X_1| + |X_2| + \dots + |X_n|$$

Analogie : Choisir un repas au Kay’s Quick Lunch en prenant soit un sandwich du menu Principal, soit un hors-d’œuvre du menu des entrées. Vous ne pouvez pas avoir les deux ; vous choisissez un seul plat.

Le principe de multiplication (règle du produit)

Si une activité se compose de $t$ étapes successives, où l'étape $i$ a $n_i$ résultats possibles, le nombre total de façons de compléter la tâche est le produit des possibilités à chaque étape :

$$N = n_1 \times n_2 \times \dots \times n_t$$

Analogie : Configurer un camion "Big Pickup". Vous devez choisir un moteur (5 options) ET un style de cabine (3 options). Le nombre total de configurations est égal à $5 \times 3 = 15$.

Implémentation en code et complexité

En informatique, ces principes se manifestent dans les structures de boucles. Les boucles séquentielles représentent le principe d'addition, tandis que les boucles imbriquées représentent le principe de multiplication.

// Principe d'addition (m + n exécutions)

pour i = 1 à m : imprimer(i)

pour j = 1 à n : imprimer(j)

// Principe de multiplication (m * n exécutions)

pour i = 1 à m :

pour j = 1 à n :

imprimer(i, j)

🎯 Principe fondamental

Distinction par mots-clés : « OU » signifie addition (choix mutuellement exclusifs), tandis que « ET » ou « successifs » signifient multiplication (étapes indépendantes dans une séquence).

QUESTION 1

Combien de dîners au Kay’s Quick Lunch (figure 6.1.1) comprennent un hors-d’œuvre et une boisson, sachant qu’il y a 3 hors-d’œuvre et 4 boissons ?

QUESTION 2

Dans le morceau de code fourni, combien de fois les instructions d'affichage sont-elles exécutées au total ? [Code : pour i = 1 à m, imprimer(i), pour j = 1 à n, imprimer(j)]

m × n

$m + n$

$m^n$

$n^m$

QUESTION 3

Combien de chaînes de longueur 3 peuvent être formées en utilisant les lettres {A, B, C, D, E} si les répétitions sont autorisées ?

125

243

QUESTION 4

En utilisant la clé publique (n=713, e=29), quelle est l'encryption du message M = 333 ?

333

557

128

712

QUESTION 5

Combien de chaînes de longueur 3 utilisant les lettres {A, B, C, D, E} contiennent la lettre A au moins une fois (répétitions autorisées) ?

125

Défi : raisonnement combinatoire avancé

Camions, triangles et trous à pigeons

Scénario : Les gros pick-up attirent parce qu'ils peuvent être personnalisés de manière apparemment infinie. Un article du New York Times suggère que vous avez besoin des compétences mathématiques de Will Hunting pour évaluer toutes les configurations. Analysons un modèle avec 5 options de moteurs (3,9L V6, 5,2L V8, 5,9L V8, 5,9L diesel turbo, 8L V10).

Définir ordre lexicographique et expliquer pourquoi il est utile dans les structures de dénombrement.

Solution : L'ordre lexicographique est une généralisation de l'ordre alphabétique des mots dans un dictionnaire aux suites de symboles ordonnés. Étant donné deux suites $a_1...a_n$ et $b_1...b_n$, nous disons que $a < b$ si, à l'indice $i$ premier où $a_i \neq b_i$, nous avons $a_i < b_i$. Il est utile car il fournit une méthode systématique pour lister toutes les permutations ou combinaisons sans omission ni répétition.

Qu'est-ce qu'une permutation de $x_1, \dots, x_n$ ? Fournissez une définition formelle.

Solution : Une permutation d'un ensemble d'objets distincts est un arrangement ordonné de ces objets. Pour un ensemble de $n$ éléments, une permutation est une bijection de l'ensemble $\{1, 2, \dots, n\}$ vers lui-même, où l'ordre des éléments dans la suite résultante compte.

Démontrer que si cinq cartes sont choisies dans un jeu standard de 52 cartes, au moins deux cartes sont de la même couleur.

Solution : Ceci est une application du principe des tiroirs. Il y a 4 couleurs possibles (les « trous ») et 5 cartes sont choisies (les « pigeons »). Puisque $5 > 4$, selon le principe des tiroirs, au moins une couleur doit contenir $\lceil 5/4 \rceil = 2$ cartes. Ainsi, au moins deux cartes doivent partager une couleur.

De combien de façons pouvons-nous sélectionner huit balles d'un sac contenant des balles rouges, bleues et jaunes (au moins huit de chaque) ? (Difficulté : mots clés : 18, Longueur : Courte)

Solution : Ceci est un problème de combinaisons avec répétition. En utilisant la formule des étoiles et barres $C(n+r-1, r)$ où $n=3$ catégories et $r=8$ choix : $C(3+8-1, 8) = C(10, 8) = C(10, 2) = (10 \times 9) / 2 = 45$ façons.